import ListNode from "../common/list_node"
import { d1,loopList ,e11,e21} from '../common/list_node'

//最短的走到头，将最长的直接合并到最后:不对，万一最短的都是最大数，这样行不通

//从h2中取值，插入h1的正确位置.
// function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
//   if(list1 == null) return list2
//   if(list2 == null) return list1
//   let newList:ListNode = list1


//   while (list2 != null) {//
//     //插入正确位置
    
//     if(list2.val <= newList.val) {//只会插入前面一个
//       let newList2_head:ListNode | null = list2.next
//       list2.next = newList

//       newList = list2
//       list2 = newList2_head
//     }else {//list2>newlist,继续比较newlist的下一个
      
//       let tmp = newList
//       while(newList != null) {

//         if(newList.next == null) {
//           newList.next = list2
//           break
//         }

//         if(list2!.val <= newList.next.val) {//拼接到newList后面
//           newList.next = list2
//           list2 = list2!.next
//           break
//         }else {//继续找newlist的正确位置
//           newList = newList.next
//         }
//       }
//       newList = tmp
//     }
//   }
//   return newList
// };

//双指针，拼接最新的
function mergeTwoLists_ptr(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if(list1 == null) return list2
  if(list2 == null) return list1

  let p1: ListNode | null = list1
  let p2: ListNode | null = list2
  let newList: ListNode | null

  if (list1.val < list2.val) {
    newList = list1
    p1 = list1.next
  }else {
    newList = list2
    p2 = list2.next
  }

  newList.next = null
  let lastNode: ListNode | null = newList
  
  //newList是已经排好序的,且是最小的，绝对不会插入。
  while(p1 != null && p2 != null){
    if(p1.val <= p2.val) {
      lastNode.next = p1
      p1 = p1.next
    }else {
      lastNode.next = p2
      p2 = p2.next
    }
    lastNode = lastNode?.next
  }


  if(p1 == null) {
    lastNode.next = p2
  }else {
    lastNode.next = p1
  }
    
  return newList

}


let newH = mergeTwoLists_ptr(e11,e21)
loopList(newH)